package leetcode.stack;

import java.util.Stack;
import stack.CandyArrayStack;

/**
 * 
 * @Title: Solution20.java 
 * @Package leetcode 
 * @Description: 问题20：括号匹配
 * @author CandyWall   
 * @date 2020年12月19日 上午9:05:22 
 * @version V1.0
 */
public class Solution20 {
    public static boolean isValid1(String s) {
    	CandyArrayStack<Character> stack = new CandyArrayStack<>();
    	//Stack<Character> stack = new Stack<>();
    	for(int i = 0; i < s.length(); i++) {
    		char c = s.charAt(i);
			if(c == ')') {
    			if(stack.isEmpty()) {
    				return false;
    			} else {
    				char c1 = stack.pop();
    				if(c1 == '(') {
    					continue;
    				} else {
    					return false;
    				}
    			}
    		}
    		if(c == ']') {
    			if(stack.isEmpty()) {
    				return false;
    			} else {
    				char c1 = stack.pop();
    				if(c1 == '[') {
    					continue;
    				} else {
    					return false;
    				}
    			}
    		}
    		if(c == '}') {
    			if(stack.isEmpty()) {
    				return false;
    			} else {
    				char c1 = stack.pop();
    				if(c1 == '{') {
    					continue;
    				} else {
    					return false;
    				}
    			}
    		}
    		stack.push(c);
    	}
    	return stack.isEmpty();
    }
    
    public static boolean isValid2(String s) {
    	Stack<Character> stack = new Stack<>();
    	for(int i = 0; i < s.length(); i++) {
    		char c = s.charAt(i);
    		if(c == '(' || c == '[' || c == '{')
    			stack.push(c);
    		else {
    			if(stack.isEmpty())
    				return false;
    			char topChar = stack.pop();
    			if(c == ')' && topChar != '(' ||
    			   c == ']' && topChar != '[' ||
    			   c == '}' && topChar != '{') 
    				return false;
    		}
    	}
    	return stack.isEmpty();
    }
    
    public static void main(String[] args) {
		System.out.println(isValid1("()[]{}"));
		System.out.println(isValid2("()[]{}"));
	}
}
